package me.timlong.Tree;

import java.util.ArrayList;
import java.util.Stack;

public class BackTraverseTree {

    //    Definition for binary tree
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    /**
     * 题目描述
     * 求给定的二叉树的后序遍历。
     * 例如：
     * 给定的二叉树为{1,#,2,3},
     *           1↵
     *         /↵  \
     *        2     3↵
     * 返回[3,2,1].
     * 备注；用递归来解这道题太没有新意了，可以给出迭代的解法么？
     *
     *
     * 解决方案：
     * 使用非递归方法实现后序遍历，则需要使用栈的数据结构，
     * 需要注意的是，先将右子节点先入栈，这样才能先访问左节点
     *
     */
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        if(null == root)
            return null;

        ArrayList<Integer> resIntegers = new ArrayList<>();
        resIntegers.addAll(postorderTraversal(root.left));
        resIntegers.addAll(postorderTraversal(root.right));
        resIntegers.add(root.val);
        return resIntegers;
    }

    public ArrayList<Integer> postorderTraversalNonRecursion(TreeNode root) {
        if(null == root)
            return null;

        ArrayList<Integer> resIntegers = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);

        TreeNode curr = root;

        TreeNode pre = null;
        while(!stack.isEmpty()){
            curr = stack.peek();

            if(null == curr.left && null == curr.right|| (null != pre && pre == curr.right || pre == curr.left)){
                resIntegers.add((curr.val));
                stack.pop();
                pre = curr;
            }
            // 注意圧栈顺序，一定是右子树先圧栈，左子树后圧栈，保证先访问左子树

            if(null != curr.right)
                stack.push(curr.right);
            if(null != curr.left)
                stack.push(curr.left);
        }
        return resIntegers;
    }


    public static void main(String[] args) {

    }
}
